#include <stdio.h>
#include <stdlib.h>

typedef struct List {
    int *data;
    int length;
    int num;
} List;

List *initList(int length)
{
    List *L = (List *)malloc(sizeof(List));
    L->length = length;
    L->data = (int *)malloc(sizeof(int) * length);
    L->num = 0;//个数初始化0
    return L;
}

void listAdd(List *L, int data)//可以判断是否超出length
{
    //if >>>>>>
    L->data[(L->num++)] = data;
}

void printList(List *L)
{
    for (int i = 0; i < L->num; i++) {
        printf("%d->", L->data[i]);
    }
    printf("NULL\n");
}

int binarySearch(List *L, int key)
{
    int start = 0;
    int end = L->num -1;//最后一个元素的索引
    int mid;
    while (start <= end) {
        mid = (start + end) / 2;
        if (key < L->data[mid]) end = mid - 1;
        else if (key > L->data[mid]) start = mid + 1;
        else return mid;
    }
    return -1;//失败标志
}

//递归实现二分查找

int binarySearch_1(List *L, int key, int low, int height)
{   //递归出口
    if (low == height) {
        if (L->data[low] == key) return low;
        else return -1;
    }
    int mid = (low + height) / 2;
    if (key < L->data[mid]) return binarySearch_1(L, key, low, mid-1);
    if (key > L->data[mid]) return binarySearch_1(L, key, mid+1, height);
    else return mid;
}

int binarySearch_2(List *L, int key, int low, int height)
{   //递归出口
    if (low <= height) {
        int mid = (low + height) / 2;
        //if (low > height) return -1; 感觉这两个留一个
        if (key < L->data[mid]) return binarySearch_1(L, key, low, mid-1);
        if (key > L->data[mid]) return binarySearch_1(L, key, mid+1, height);
        else return mid;
    }
    return -1;
}

int main(void)
{
    List *L = initList(10);
    listAdd(L, 1);
    listAdd(L, 2);
    listAdd(L, 3);
    listAdd(L, 4);
    listAdd(L, 5);
    listAdd(L, 6);
    listAdd(L, 7);
    listAdd(L, 8);
    listAdd(L, 9);
    listAdd(L, 10);
    printList(L);
    int test = binarySearch_2(L, 8, 0, 10);
    printf("%d\n", test);

    return 0;
} 